
/**
 * 
 * 服务器广播
 * 
 * 题目描述

服务器连接方式包括直接相连，间接相连。A和B直接连接，B和C直接连接，则A和C间接连接。

直接连接和间接连接都可以发送广播。

给出一个 N * N 数组，代表 N 个服务器

matrix[i][j] == 1，则代表 i 和 j 直接连接，不等于1时，代表 i 和 j 不直接连接
matrix[i][i] == 1, 即自己和自己直接连接
matrix[i][j] == matrix[j][i]
计算初始需要给几台服务器广播，才可以使每个服务器都收到广播。

输入描述
输入为 N 行，每行有 N 个数字，为 0 或 1，由空格分隔，构成N * N的数组

N 的范围为 1 ≤ N ≤ 40
输出描述
输出一个数字，为需要广播的服务器的数量

用例
输入	1 0 0
0 1 0
0 0 1
输出	3
说明	3台服务器互不连接，所以需要分别广播这3台服务器
输入	1 1
1 1
输出	1
说明	2台服务器互相连接，所以只需要广播其中一台服务器

 * 
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

/**
  * 
  题目解析
本题其实就是要我们求解图中连通分量个数，可以使用并查集解题。

关于并查集的视频教程可以看：

《算法训练营》进阶篇 01 并查集_哔哩哔哩_bilibili
  */
public class 服务器广播 {
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in).useDelimiter("[,\n]");
 
        ArrayList<int[]> matrix = new ArrayList<>();
        while (sc.hasNextLine()) { // 本地IDE测试时，控制台输入完数据后，另起一行键入ctrl+d或者ctrl+z即可结束循环
            
            try{

                int[] row = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
                matrix.add(row);

            }catch(Exception e){

                break;
            }
        }
 
        System.out.println(getResult(matrix));
    }
 
    public static int getResult(ArrayList<int[]> matrix) {
        int n = matrix.size();
 
        UnionFindSet ufs = new UnionFindSet(n);
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix.get(i)[j] == 1) {
                    ufs.union(i, j);
                }
            }
        }
 
        return ufs.getCount();
    }

    // 并查集实现
private static class UnionFindSet {
    public int[] fa;
    private int count;
 
    public UnionFindSet(int n) {
        this.fa = new int[n];
        for (int i = 0; i < n; i++) fa[i] = i;
        this.count = n;
    }
 
    public int find(int x) {
        if (x != this.fa[x]) {
            this.fa[x] = this.find(this.fa[x]);
            return this.fa[x];
        }
        return x;
    }
 
    public void union(int x, int y) {
        int x_fa = this.find(x);
        int y_fa = this.find(y);
 
        if (x_fa != y_fa) {
            this.fa[y_fa] = x_fa;
            this.count--;
        }
    }

    public int getCount(){

        return this.count;
    }

}
}
